\part{图论}

\chapter{图的基本概念}

\section{图}

\begin{itementry}
    无序积:对于两个集合\(A,B\),我们称\(\{\{a,b\}\mid a\in A\wedge b\in B\}\)为\(A\)与\(B\)的无序积,记为\(A\&B\)
\end{itementry}

\begin{itementry}
    无向图\&顶点集\&顶点集\&顶点/结点\&边集\&无向边:若一个有序二元组\(\left<V,E\right>\)满足:
    \begin{theitem}
        \item \(V\)是一个非空有穷集,称为顶点集,其元素称为顶点或节点
        \item \(E\)是无序积\(V\&V\)的有穷多重子集(即元素可重复出现),称为边集,其元素称为无向边,也简称为边
    \end{theitem}
    则称这样的二元组\(\left<V,E\right>\)为一个无向图\(G\)
    \begin{subentry}
        特别地,我们以\(V(G),E(G)\)分别表示\(G\)的顶点集与边集,用\(|V(G)|,|E(G)|\)表示\(G\)的定点数与边数
    \end{subentry}
\end{itementry}

\begin{itementry}
    有向图:若一个有序二元组\(\left<V,E\right>\)满足:
    \begin{theitem}
        \item \(V\)是一个非空有穷集,称为顶点集,其元素称为顶点或节点
        \item \(E\)是笛卡尔积\(V\times V\)的有穷多重子集,称为边集,其元素称为有向边
    \end{theitem}
    则称这样的二元组\(\left<V,E\right>\)为有向图\(D\)
\end{itementry}

\begin{itementry}
    图\&阶:无向图与有向图统称为图.一个图的定点数称为图的阶
\end{itementry}

\begin{itementry}
    零图\&平凡图:没有边的图称为零图.\(n\)阶零图记为\(N_n\),称\(N_1\)为平凡图
\end{itementry}

\begin{itementry}
    空图:我们将顶点集为空集的图称为空图,记为\(\emptyset\)
\end{itementry}

\begin{itementry}
    标定图:若一个图的每一个点与边都被用符号指定,则称这样的图为标定图
\end{itementry}

\begin{itementry}
    基图:对于一个有向图\(D\),将其有向边全部改为无向边得到的图\(G\)称为其基图
\end{itementry}

\begin{itementry}
    关联\&关联次数\&环:设\(G=\left<V,E\right>\)是无向图,若\(e_k=(v_i,\*v_j)\*\in E\),则称\(v_i,v_j\)是\(e_k\)的端点,\(e_k\)与\(v_i(v_j)\)关联.若\(v_i\neq v_j\),则称\(e_k\)与\(v_i\)的关联次数为1,若\(v_i=v_j\),则称\(e_k\)与\(v_i\)的关联次数为2,并称\(e_k\)为环,若\(v_i\)与\(e_k\)不关联,则称\(e_k\)与\(v_i\)的关联次数为0
\end{itementry}

\begin{itementry}
    相邻:在无向图中,若两个顶点\(v_i,v_j\)之间有一条边连接,则称这两个顶点相邻.若两条边至少有一个公共端点,则称这两条边相邻
\end{itementry}

\begin{itementry}
    端点\&始点\&终点\&关联\&环:设\(D=\left<V,E\right>\)是有向图,\*\(e_k=(v_i,v_j)\in E\),则称\(v_i,v_j\)为\(e_k\)的顶点,且称\(v_i,v_j\)关联,分别称\(v_i,v_j\)为\(e_k\)的始点和终点,若\(v_i=v_j\),则称\(e_k\)是\(D\)中的环
\end{itementry}

\begin{itementry}
    相邻:在有向图中,若两个顶点\(v_i,v_j\)之间有一条边连接,则称这两个顶点相邻.若两条边中一条的终点是另一条的起点,则称这两条边相邻
\end{itementry}

\begin{itementry}
    孤立点:图中没有边关联的顶点称为孤立点
\end{itementry}

\begin{itementry}
    邻域\&闭邻域\&关联集:对于无向图\(G=\left<V,E\right>\)和\(v\in V\),我们分别称
    \begin{gather*}
        N_G(v)=\{u\mid u\in V\wedge(u,v)\in E\wedge u\neq v\}\\
        \overline{N_G}(v)=N_G(v)\cup\{v\}\\
        I_G(v)=\{e\mid e\in E\wedge e\text{与}v\text{关联}\}
    \end{gather*}
    为\(v\)的邻域,闭邻域,关联集
\end{itementry}

\begin{itementry}
    后继元素\&先驱元素\&邻域\&闭邻域:对于有向图\(D=\left<V,E\right>\)和\(v\in V\),我们分别称
    \begin{gather*}
        \Gamma^+_D(v)=\{u\mid u\in V\wedge(v,u)\in E\wedge u\neq v\}\\
        \Gamma^-_D(v)=\{u\mid u\in V\wedge(u,v)\in E\wedge u\neq v\}\\
        N_D(v)=\Gamma^+_D(v)\cup\Gamma^-_D(v)\\
        \overline{N_D}(v)=N_D(v)\cup\{v\}
    \end{gather*}
    为\(v\)的后继元素,先驱元素,邻域,闭邻域
\end{itementry}

\begin{itementry}
    平行边\&多重图\&重数\&简单图:再无向图中,若关联一对顶点的无向边多于一条,则称这些边为平行边,平行边的条数称为重数.含平行边的图称为多重图,不含平行边与环的图称为简单图
    \begin{subentry}
        特别地,对于有向图的平行边,还需始点终点相同
    \end{subentry}
\end{itementry}

\begin{itementry}
    度数/度\&出度\&入度:对于无向图\(G\)的一端点\(v\),我们将\(v\)作为边的端点的次数称为\(v\)的度数,简称为度,记为\(d_G(v)\),有时也记为\(d(v)\).
    \begin{subentry}
        特别地,对于有向图,还有出度,入度的概念,分别记为\(d^+(v),d^-(v)\)
    \end{subentry}
\end{itementry}

\begin{itementry}
    最大度\&最小度:对于无向图\(G\),我们分别称
    \begin{align*}
        \Delta(G)=\max\{d(v)\mid v\in V(G)\}\\
        \delta(G)=\min\{d(v)\mid v\in V(G)\}
    \end{align*}
    为\(G\)的最大度与最小度.
    \begin{subentry}
        特别地,对于有向图,有最大出度,最大入度等概念,此处略
    \end{subentry}
\end{itementry}

\begin{itementry}
    悬挂顶点\&悬挂边\&偶度顶点\&奇度顶点:我们将度数为1的顶点称为悬挂顶点,将与它关联的边称为悬挂边.度为奇数(偶数)的顶点称为奇(偶)度顶点
\end{itementry}

\begin{itementry}
    握手定理:在所有的有向图中,所有顶点的度数之和等于边数的2倍,所有顶点的入度之和等于所有顶点的出度之和等于边数
\end{itementry}

\begin{itementry}
    度数列\&出度列\&入度列\&可图化\&可简单图化:设\(G=\left<V,E\right>,V=\{v_1,\dots,v_n\}\),我们称\(d(v_1),\dots,d(v_n)\)为\(G\)的出度列.对于顶点标定的无向图,其度数列是唯一的.反正,对于给定的整数列,若存在一无向图使得该数列为其度数列,则称这整数列是可图化的.若得到的图是简单图,则称其为可简单图化的.
    \begin{subentry}
        特别地,对于有向图,还有出度列与入度列
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:非负整数列\(d=(d_1,\dots,d_n)\)可图化当且仅当\(\sum d_n\)为偶数
\end{itementry}

\begin{itementry}
    定理:设\(G\)为任意\(n\)阶无向图,则\(\Delta(G)\leq n-1\)
\end{itementry}

\begin{itementry}
    同构设\(G_1=\left<V_1,E_1\right>\),\(G_2=\left<V_2,E_2\right>\)为两个无向图,若存在一双射\(f:V_1\to V_2\),使得\(v_i,v_j\in V_1\),\((v_i,v_j)\in E_1\)的充要条件为\((f(v_i),f(v_j))\in E_2\).且\((v_1,v_j)\)与\((f(v_i),f(v_j))\)的重数相同,则称\(G_1\)与\(G_2\)同构,记为\(G_1\cong G_2\)
\end{itementry}

\begin{itementry}
    无向完全图\&有向完全图\&竞赛图:
    \begin{theitem}
        \item 设\(G\)是\(n\)阶无向简单图,若\(G\)中每个顶点均与其余\(n-1\)个顶点相邻,则称\(G\)是\(n\)阶无向完全图,记为\(K_n\).
        \item 设\(D\)是\(n\)阶有向简单图,若\(D\)中每个顶点均与其余\(n-1\)个顶点都有两个方向的连接,则称\(D\)是\(n\)阶有向完全图
        \item 设\(D\)为\(n\)阶简单图,若\(D\)的基图是\(n\)阶无向完全图\(K_n\),则称\(D\)为\(n\)阶竞赛图
    \end{theitem}
\end{itementry}

\begin{itementry}
    \(k\)-正则图:设\(G\)是\(n\)阶无向简单图,若\(\forall v\in V(G)\),均有\(d(v)=k\),则称\(G\)为\(k\)-正则图
\end{itementry}

\begin{itementry}
    子图\&母图\&真子图\&生成子图:设\(G=\left<V,E\right>,G'=\left<V',\*E'\right>\)为两个图(同为有向或无向).若\(V'\subseteq V\)且\(E'\subseteq E\),则称\(G'\)为\(G\)的子图,\(G\)为\(G'\)的母图,记为\(G'\subseteq G\).又若\(V'\subset V\)或\(E'\subset E\),则称\(G'\)为\(G\)的真子图.若\(V'=V\),则称\(G'\)为\(G\)的生成子图
\end{itementry}

\begin{itementry}
    导出的子图:设\(G=\left<V,E\right>\),\(V_1\subset V\)且\(V_1\neq\emptyset\),则称以\(V_1\)为顶点集,以\(G\)中两个端点都在\(V_1\)中的边组成边集\(E_1\)的图为\(G\)的\(V_1\)导出的子图,记为\(G[V_1]\).若\(E_1\subset E\)且\(E_1\neq\emptyset\),则称以\(E_1\)中边关联的顶点为顶点集,\(E_1\)为边集的图为\(G\)的\(E_1\)导出的子图,记为\(G[E_1]\)
\end{itementry}

\begin{itementry}
    补图\&自补图:设\(G=\left<V,E\right>\)是\(n\)阶无向简单图,令\(\overline{E}=\{(u,v)\mid u\in V\wedge v\in V\wedge u\neq v\wedge(u,v)\notin E\}\),称\(\overline{G}=\left<\mathstrut\smash{V,\overline{E}}\right>\)为\(G\)的补图
    \begin{subentry}
        特别地,若\(G\cong\overline{G}\),则称\(G\)为自补图
    \end{subentry}
\end{itementry}

\begin{itementry}
    删除:设\(G=\left<V,E\right>\),\(e\in E\),用\(G-e\)表示从\(G\)中去掉\(e\),称为删除边\(e\),又设\(E'\subset E\),用\(G-E'\)表示从\(G\)中删除\(E'\)的所有边,称为删除\(E'\).设\(v\in V\),用\(G-v\)表示从\(G\)中去掉点\(v\)及其关联的一切边,称为删除顶点\(v\).又设\(V'\subset V\),用\(G-V'\)表示从\(G\)中删除\(V'\)中所有的顶点,称为删除\(V'\)
\end{itementry}

\begin{itementry}
    收缩:设\(G=\left<V,E\right>\),\(e=(u,v)\in E\),用\(G\backslash e\)表示从\(G\)中删除\(e\)后,将\(e\)的两个端点\(u,v\)用一个新顶点\(w\)代替,并使\(w\)关联除\(e\)以外\(u,v\)关联的所有边,称为边\(e\)的收缩
\end{itementry}

\begin{itementry}
    新加边:设\(G=\left<V,E\right>\),\(u,v\in V\)(\(u,v\)可以相邻也可不相邻),用\(G\cup(u,v)\)或\(G+(u,v)\)表示再\(u,v\)之间加一条边\((u,v)\),称为新加边
\end{itementry}

\section{通路与回路}

\begin{itementry}
    通路\&始点\&终点\&长度\&回路:设\(G\)是无向标定图,\(G\)中顶点与边的交替序列\(\Gamma=v_{i_0}e_{j_1}\cdots e_{j_l}v_{i_l}\)称作从\(v_{i_0}\)到\(v_{i_l}\)的同理,其中\(v_{i_{r-1}}\),\(v_{i_r}\)是\(e_{j_{r}}\)的端点,\(r=1,\dots,l\).\(v_{i_0},v_{i_l}\)分别称为\(\Gamma\)的始点与终点.\(\Gamma\)中边的条数称为其长度,若有\(v_{i_0}=v_{i_l}\),则称\(\Gamma\)为回路
\end{itementry}

\begin{itementry}
    简单通路\&简单回路\&初级通路/路径\&初级回路/图\&奇圈\&偶圈:对于通路\(\Gamma\),若\(\Gamma\)的所有边各异,则称\(\Gamma\)为简单通路,若所有顶点各异(允许始点终点相同),所有边也各异,则称\(\Gamma\)为初级通路或路径.若初级通路的起点终点相同,则称其为初级回路或圈.长度为奇数的圈称为奇圈,长度为偶数的圈称为偶圈
\end{itementry}

\begin{itementry}
    复杂通路:对于同理\(\Gamma\),若其中有边重复出现,则称\(\Gamma\)为复杂通路,若又有\(v_{i_0}=v_{i_l}\),则称\(\Gamma\)为复杂回路
    \begin{subentry}
        特别地,在有向图中也有相应的概念,但需要同向边方向一致
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:在\(n\)阶图\(G\)中,若从顶点\(u\)到\(v(u\neq v)\)存在通路,则从\(u\)到\(v\)存在长度小于等于\(n-1\)的通路
\end{itementry}

\begin{itementry}
    定理:在\(n\)阶图\(G\)中,若存在\(v\)到自身的回路,则一定存在\(v\)到自身长度小于等于\(n\)的回路
\end{itementry}

\section{图的连通性}

\begin{itementry}
    连通:设无向图\(G=\left<V,E\right>\),若\(u,v\)之间存在通路,则称\(u,v\)是连通的,记为\(u\sim v\),且规定\(\forall v\in V\),\(v\sim v\)
    \begin{subentry}
        特别地,连通构成等价关系
    \end{subentry}
\end{itementry}

\begin{itementry}
    连通图:若无向图\(G\)是平凡图或\(G\)中任何两个顶点连通,则称\(G\)为连通图,否则称为非连通图
\end{itementry}

\begin{itementry}
    连通分支:设无向图\(G=\left<V,E\right>\),\(V_i\)是\(V\)关于顶点之间的联通关系\(\sim\)的一个等价类,称导出子图\(G[V_i]\)为\(G\)的一个连通分支.\(G\)的连通分支数记为\(p(G)\)
\end{itementry}

\begin{itementry}
    短程线\&距离:设\(u,v\)为无向图\(G\)中任意两个顶点,若\(u\sim v\),则称\(u,v\)之间长度最短的通路为\(u,v\)之间的短程线,短程线的长度称为\(u,v\)之间的距离,记为\(d(u,v)\),当\(u,v\)不连通时,规定\(d(u,v)=\infty\)
    \begin{subentry}
        特别地,此处距离满足距离空间中距离定义
    \end{subentry}
\end{itementry}

\chapter{欧拉图与哈密顿图}

\chapter{树}

\chapter{平面图}

\chapter{支配集,覆盖集,独立集,匹配与着色}